package BinaryTreePackage;

import TreePackage.Tree;
import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * @author Lzm
 * @version 1.0
 */
public class BinaryTree {
  @Test
  public void levelOrderTest(){
    TreeNode node1 = new TreeNode(6);
    TreeNode node2 = new TreeNode(4);
    TreeNode node3 = new TreeNode(7);
    TreeNode node4 = new TreeNode(1);
    TreeNode node5 = new TreeNode(3);
    TreeNode node6 = new TreeNode(5);
    TreeNode node7 = new TreeNode(8);

    node1.left = node2;
    node1.right = node3;
    node2.left = node4;
    node2.right = node5;
    node3.left = node6;
    node3.right = node7;
    List<List<Integer>> lists = levelOrder(node1);
    System.out.println(lists);
  }


  public List<List<Integer>> levelOrder(TreeNode root) {
    /*创建队列*/
    Queue<TreeNode> queue = new LinkedList<>();

    List<List<Integer>> result = new ArrayList<>();
    if (root == null){
      return result;
    }
    /*将根节点入队列*/
    queue.add(root);
    /*定义一个变量来记录每层树的节点个数*/
    int size = queue.size();
    while(queue.size() != 0){
      size = queue.size();
      List<Integer> list = new ArrayList<>();
      while(size-- > 0){
        /*从队列中弹出节点*/
        TreeNode node = queue.poll();
        /*将弹出的节点加入到list中*/
        list.add(node.val);
        /*将此节点的左右节点都加入到队列中*/
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
      }
      result.add(list);
    }
    return result;
  }

  /*
  * 递归三部曲:
  * 1. 判断返回类型和参数 (返回类型:树的根节点, 参数:要翻转的树的根节点)
  * 2. 递归的结束条件 (节点为空)
  * 3. 每层的逻辑 (左右子节点交换)
  * */
  public TreeNode invertTree(TreeNode root) {
      /*判断根节点是否为空*/
    if (root == null){
      return root;
    }
    /*交换左右子节点*/
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    if (root.left != null) invertTree(root.left);
    if (root.right != null) invertTree(root.right);
    return root;
  }
  /*
  * 判断一个二叉树是否对称
  * 思路 : 判断二叉树翻转后是否与原二叉树相同
  * 递归三部曲 : 确定传入参数和返回值
  *            确定递归结束条件
  *            确定单层逻辑 (判断左右子树是否相同)
  * 每次return都是返回上一个节点
  *
  * */
  public boolean compare(TreeNode left, TreeNode right) {

      /*选择后序遍历, 这样才能加左右子树的对比结果返回给父节点*/
      /*给出结束条件*/
    if (left == null && right != null){
      return false;
    }
    else if (left != null && right == null){
      return false;
    }
    else if ((left != null && right != null) && left.val != right.val){
      return false;
    }
    else if (left == null && right == null){
      return true;
    }
    boolean leftResult = compare(left.left,right.right);
    boolean rightResult = compare(left.right,right.left);
    return leftResult && rightResult;
  }

  /*
  * 功能 : 求得二叉树的最大深度
  * 参数 : 二叉树的根节点
  * 递归三部曲 : 确定传入参数和返回值
  *            确定递归结束条件 (root == null)
  *            确定单层逻辑 (取左子树和右子树的高度最大值)
  * 每次return都是返回上一个节点
  * */
  public int maxDepth(TreeNode root) {
      if (root == null){
        return 0;
      }
      /*递归结束条件*/
    if (root == null){
      return 0;
    }
    /*单层递归逻辑*/
    int leftHeight = maxDepth(root.left);
    int rightHeight = maxDepth(root.right);
    int result = 1 + Math.max(leftHeight,rightHeight);
    return result;
  }
  /*
  *
  *
  * */
  public int minDepth(TreeNode root) {
      if (root == null){
        return 0;
      }
      int leftHeight = 0;
      int rightHeight = 0;
      int result = 0;
      if (root.left == null && root.right != null){
        return 1 + rightHeight;
      }

      if (root.left != null && root.right == null){
        return 1 + leftHeight;
      }
      if (root.left == null && root.right == null){
        result = 1 + Math.min(leftHeight,rightHeight);
      }
      return result;
  }

  /*
  * 功能 : 返回此节点的最大高度
  * 参数 : 要求的最大高度的节点
  * */
  public static int getHeight(TreeNode root) {
      /*终止条件*/
    if (root == null){
      return 0;
    }
    /*左子树的高度*/
    int leftHeight = getHeight(root.left);
    /*如果左子树不是一个平衡二叉树则向此root节点返回-1*/
    if (leftHeight == -1) return -1;
    /*右子树的高度*/
    int rightHeight = getHeight(root.right);
    /*如果右子树不是一个平衡二叉树则向此root节点返回-1*/
    if (rightHeight == -1) return -1;

    /*如果左右子树的高度差大于1, 则返回-1*/
    if (Math.abs(leftHeight - rightHeight) > 1) return -1;
    /*反之返回左右子树的最大高度*/
    return 1 + Math.max(leftHeight,rightHeight);
  }
  public int countNodes(TreeNode root) {
      if (root == null){
        return 0;
      }
      TreeNode left = root.left;
      TreeNode right = root.right;
      int leftDepth = 0;
      int rightDepth = 0;
      while(left != null){
        left = left.left;
        leftDepth++;
      }
    while(right != null){
      right = right.right;
      rightDepth++;
    }
    if (leftDepth == rightDepth){
      return (2 << leftDepth) - 1;
    }
    int leftNumber = countNodes(root.left);
    int rightNumber = countNodes(root.right);
    return leftNumber + rightNumber + 1;
  }
  public int sumOfLeftLeaves(TreeNode root) {
      /*判断终止条件*/
    if (root == null){
      /*若此节点为null, 那这个节点的左子树节点为0*/
      return 0;
    }
    if (root != null && root.left == null && root.right == null){
      /*若此节点是叶子节点, 那这个节点无左子树, 返回0*/
      return 0;
    }
    /*单层递归的逻辑*/
    int leftNumber = sumOfLeftLeaves(root.left);
    /*如果这个节点不为null, 且其左子节点不是叶子节点, 则返回其节点的左子树之和*/
    if (root.left != null && root.left.left == null && root.left.right == null){
      leftNumber = root.left.val;
    }
    int rightNumber = sumOfLeftLeaves(root.right);
    return rightNumber + leftNumber;
  }



  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode() {
    }

    public TreeNode(int val) {
      this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
  }
}
